package com.baixiaowen.xiaoaointerview.Java编程功底篇.手写链表算法;

import java.util.HashSet;
import java.util.Set;
import java.util.function.Predicate;

public class List<T> {

    static class Node<T> {
        Node<T> next = null;
        T data;
        public Node(T data) {
            this.data = data;
        }
    }

    Node<T> head = null;

    // O(1)
    public void insert(T data) {
        Node<T> node = new Node<>(data);
        node.next = head;
        head = node;
    }

    // O(n)
    public Node<T> find(Predicate<T> predicate) {
        Node<T> p = this.head;
        while (p != null) {
            if (predicate.test(p.data)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public void remove(Node<T> node) {
        if (head == null) {
            return;
        }

        if (head == node) {
            head = head.next;
            return;
        }

        Node<T> slow = head;
        Node<T> fast = head.next;

        while (fast != node && fast != null) {
            slow = fast;
            fast = fast.next;
        }

        if (fast != null) {
            // fast -> data
            slow.next = fast.next;
//            fast.data = null;
        }
    }

    public Integer size(){
        Node<T> p = head;
        Integer c = 0;
        while(p != null) { p = p.next; c++; }
        return c;
    }

    // 链表反转 - 遍历， 比较难理解
    public void reverse() {
        // prev | current | next

        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    // 链表反转 - 递归实现
    private Node<T> _reverse2(Node<T> head) {

        if (head == null || head.next == null) {
            return head;
        }

        Node<T> rest = _reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }

    public void reverse2() {
        head = _reverse2(head);
    }


    // 判断链表中是否有环的问题 - 使用HashSet来实现
    // 缺点: 空间复杂度很高 O(n)
    public boolean hasLoop1() {
        Set set = new HashSet();

        Node<T> p = head;
        while (p != null) {
            if (set.contains(p)) {
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;
    }

    // 判断链表中是否有环的问题 - 利用快慢指针来实现， 空间复杂度为 O(1)
    public boolean hasLoop2() {
        // fast 每次走两个，slow 每次走一个，fast 能不能追上 slow
        if (head == null || head.next == null) {
            return false;
        }

        Node<T> slow = head;
        Node<T> fast = head.next.next;
        while (fast != null && fast.next != null) {
            if (fast == slow) {return true;}
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }

    public static void main(String[] args) {
//        test_insert();
//        test_find_remove();
//        test_reverse();
        test_loop();
    }

    public static void test_find_remove() {
        List<String> list = new List<>();

        list.insert("C++");
        list.insert("Java");
        list.insert("C");
        list.insert("C#");
        list.insert("python");

        Node<String> node = list.find(x -> x == "Java");
        if (!"Java".equals(node.data)) {
            System.err.println("链表查询有误");
        }

        Node<String> node1 = list.find(x -> x == "Java");
        if ("Ruby".equals(node1.data)) {
            System.err.println("链表查询有误");
        }

        list.remove(node);
        if (4 != list.size()) {
            System.err.println("链表删除有误");
        }
        if (null != list.find(x -> x == "Java")) {
            System.err.println("链表删除有误");
        }
    }

    public static void test_insert() {
        List<Integer> list = new List<>();
        list.insert(1);
        list.insert(2);
        list.insert(3);

        Node<Integer> p = list.head;
        for (Integer i = 3; p != null; i--) {
            if (i.intValue() == p.data) {
                p = p.next;
            } else {
                try {
                    throw new Exception("链表有问题");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void test_reverse() {
        List<Integer> list = new List<>();

        list.insert(1);
        list.insert(2);
        list.insert(3);

//        list.reverse();
        list.reverse2();

        Node<Integer> p = list.head;
        for (Integer i = 1; p != null; i ++) {
            if (i.intValue() != p.data) {
                System.err.println("链表反转错误");
            } else {
                p = p.next;
            }
        }

    }

    public static void test_loop() {
        List<Integer> list = new List<>();
        list.insert(3);
        list.insert(2);
        list.insert(1);
        list.insert(0);

        Node<Integer> node = list.find(x -> x == 3);

        node.next = list.head;

        if (list.hasLoop1()) {
            System.err.println("链表存在环");
        }
        if (list.hasLoop2()) {
            System.err.println("链表存在环");
        }
    }

}
